using System;
using System.Diagnostics;

using FineCollection.Intf;


namespace FineCollection.Immutable
{

    /// <summary>
    /// Immutable collections manipulation.
    /// Contains static functions for manipulate with collections.
    /// </summary>
    public static class imc
    {
        
        /// <summary>
        /// Performs the union of the two ordered sets.
        /// </summary>
        /// <typeparam name="T">type of an item.</typeparam>
        /// <param name="set1">the first set (can be null or empty).</param>
        /// <param name="set2">the second set (can be null or empty).</param>
        /// <returns>immutable union of the specified sets.</returns>
        /// <remarks>
        /// <para>
        /// The result set will contain all items that are present in both sets.
        /// So, the number of result items will be from <i>max(n1,n2)</i> to <i>n1 + n2</i>
        /// inclusive.
        /// </para>
        /// <para>
        /// This function implements a sorted merge algorithm (without sort -
        /// both sets are already ordered), 
        /// and the complexity of this method id <i>o(n)</i>,
        /// where <i>n</i> is a number of items in both sets.
        /// </para>
        /// <para>
        /// In case when one set includes another one, and the largest one
        /// is immutable and ordered, this function returns the first one
        /// without making a copy.
        /// </para>
        /// </remarks>
        public static RRandomSet<T> Union<T>(ROrderSet<T> set1, ROrderSet<T> set2)
            where T: IComparable<T>
        {
            int n1 = set1 != null ? set1.Count : 0,
                n2 = set2 != null ? set2.Count : 0;

            if (n1 == 0 && n2 == 0)
            {
                return ImmOrderZero<T>.zero;
            }
            else if (n1 > 0 && n2 == 0)
            {
                if (set1 is RImmutable && set1 is RRandomSet<T>)
                    return set1 as RRandomSet<T>;
                else
                    return MakeAppropriateCopy(set1);
            }
            else if (n2 > 0 && n1 == 0)
            {
                if (set2 is RImmutable && set2 is RRandomSet<T>)
                    return set2 as RRandomSet<T>;
                else
                    return MakeAppropriateCopy(set2);
            }
            else
            {
                return Merge(set1, set2);
            }

        }


        private static RRandomSet<T> Merge<T>(ROrderSet<T> set1, ROrderSet<T> set2)
            where T : IComparable<T>
        {
            int n1 = set1.Count,
                n2 = set2.Count;
            int limit = n1 + n2,
                k = 0;

            T[] arr = new T[limit];

            RIterator<T> it1 = set1.TakeIterator(),
                         it2 = set2.TakeIterator();
            bool ex1 = it1.Next(),
                 ex2 = it2.Next();
            
            while (ex1 && ex2)
            {
                int z = Math.Sign( it1.Current.CompareTo(it2.Current) );
                switch (z)
                {
                    case -1:
                        arr[k++] = it1.Current;
                        ex1 = it1.Next();
                        break;
                    case +1:
                        arr[k++] = it2.Current;
                        ex2 = it2.Next();
                        break;
                    case 0:
                        arr[k++] = it1.Current;
                        ex1 = it1.Next();
                        ex2 = it2.Next();
                        break;
                }
            }

            while (ex1)
            {
                arr[k++] = it1.Current;
                ex1 = it1.Next();
            }

            while (ex2)
            {
                arr[k++] = it2.Current;
                ex2 = it2.Next();
            }

            RRandomSet<T> result;

            // if set1 contains all items of set2
            if (k == n1 && n1 >= n2 && set1 is RRandomSet<T>)
                result = set1 as RRandomSet<T>;
            // if set2 contains all items of set1
            else if (k == n2 && n2 >= n1 && set2 is RRandomSet<T>)
                result = set2 as RRandomSet<T>;
            // in other case
            else
                result = new ImmSortSet<T>(arr, k, true);

            return result;
        }


        /// <summary>
        /// Performs the intersection of two ordered sets.
        /// </summary>
        /// <typeparam name="T">type of an item.</typeparam>
        /// <param name="set1">the first set (can be null or empty).</param>
        /// <param name="set2">the second set (can be null or empty).</param>
        /// <returns>immutable intersection of the specified sets.</returns>
        /// <remarks>
        /// <para>
        /// The result is a set where each item presents in both specified sets.
        /// So, the number of result items will be from <i>0</i> to <i>min(n1, n2)</i>
        /// inclusive.
        /// </para>
        /// <para>
        /// This method implements the optimized nested-loops with binary serach algorithm.
        /// Its complexity is <i>o( (m + 2) ln(n1 + n2) )</i>, where <i>m</i> is a number
        /// of items in the result set.
        /// </para>
        /// <para>
        /// In case when one set includes another one, and the largest one
        /// is immutable and ordered, this function returns the first one
        /// without making a copy.
        /// </para>
        /// </remarks>
        public static RRandomSet<T> Intersect<T>(ROrderSet<T> set1, ROrderSet<T> set2)
            where T : IComparable<T>
        {
            int n1 = set1 != null ? set1.Count : 0,
                n2 = set2 != null ? set2.Count : 0;

            if (n1 == 0 || n2 == 0)
                return ImmOrderZero<T>.zero;

            return FastJoin(set1, set2);
        }


        private static RRandomSet<T> FastJoin<T>(ROrderSet<T> set1, ROrderSet<T> set2)
            where T : IComparable<T>
        {
            int n1 = set1.Count,
                n2 = set2.Count;
            int limit = Math.Min(n1, n2),
                rn = 0;
            
            T[] resultArray = null;

            ROrderIterator<T> it1 = set1.TakeIterator(),
                              it2 = set2.TakeIterator();
            it1.Next();
            it2.Next();

            while (it1.Where < +1 && it2.Where < +1) // while both are active
            {
                int z = Math.Sign( it1.Current.CompareTo(it2.Current) );
                switch(z)
                {
                    case 0:
                        if (resultArray == null)
                            resultArray = new T[limit];
                        resultArray[rn++] = it1.Current;
                        it1.Next();
                        it2.Next();
                        break;

                    case -1:
                        it1.Jump(it2.Current);
                        break;

                    case +1:
                        it2.Jump(it1.Current);
                        break;
                }
            }

            if (n1 == rn && set1 is RImmutable && set1 is RRandomSet<T>) // the result is exactly first set
                return set1 as RRandomSet<T>;
            if (n2 == rn && set2 is RImmutable && set2 is RRandomSet<T>) // the result is exactly second set
                return set2 as RRandomSet<T>;

            return MakeAppropriateCopy(resultArray, rn, true);
        }



        /// <summary>
        /// Performs the mathematical difference between the <c>minuend</c> 
        /// and the <c>subtrahend</c>. In other words, this functions returns 
        /// the set contains items from the <c>minuend</c> that don't present
        /// in the <c>subtrahend</c>.
        /// </summary>
        /// <typeparam name="T">type of an item.</typeparam>
        /// <param name="minuend">minuend of a difference.</param>
        /// <param name="subtrahend">subtrahend of a difference.</param>
        /// <returns>the difference.</returns>
        public static RRandomSet<T> Difference<T>(ROrderSet<T> minuend, ROrderSet<T> subtrahend)
            where T : IComparable<T>
        {
            int n1 = minuend != null ? minuend.Count : 0,
                n2 = subtrahend != null ? subtrahend.Count : 0;
            
            if (n1 == 0)
                return ImmOrderZero<T>.zero;

            if (n2 == 0)
            {
                if (minuend is RImmutable && minuend is RRandomSet<T>)
                    return minuend as RRandomSet<T>;
                else
                    return new ImmSortSet<T>(minuend);
            }

            throw new NotImplementedException();
        }


        private static RRandomSet<T> MakeAppropriateCopy<T>(ROrderSet<T> set)
            where T : IComparable<T>
        {
            int n = set.Count;
            switch (n)
            {
                case 0:
                    return ImmOrderZero<T>.zero;
                case 1:
                    return new ImmOrderOne<T>(set.First);
                default:
                    return new ImmSortSet<T>(set);
            }
        }


        // <param name="arr">must be a sorted array!</param>
        private static RRandomSet<T> MakeAppropriateCopy<T>(T[] arr, int count, bool takeOwnership)
            where T : IComparable<T>
        {
            if (count > 0)
                Debug.Assert(count <= arr.Length);

            switch (count)
            {
                case 0:
                    return ImmOrderZero<T>.zero;
                case 1:
                    return new ImmOrderOne<T>(arr[0]);
                default:
                    return new ImmSortSet<T>(arr, count, takeOwnership);
            }
        }


    }

}